/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {//随机链表复制
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(pHead==NULL)
            return NULL;
        RandomListNode* oldList=pHead;
        while(oldList!=NULL)//在每个结点之后复制一个结点
        {
            RandomListNode* newList=new RandomListNode(oldList->label);
            newList->next=oldList->next;
            oldList->next=newList;
            oldList=newList->next;
        }
        
        oldList=pHead;
        RandomListNode* newList;
        while(oldList!=NULL)//复制随机结点
        {
            newList=oldList->next;
            if(oldList->random!=NULL)
                newList->random=oldList->random->next;
            oldList=newList->next;
        }
        
        oldList=pHead;
        RandomListNode* newHead=pHead->next;
        while(oldList!=NULL)//拆分成新旧两个链表
        {
            newList=oldList->next;
            oldList->next=newList->next;
            if(oldList->next!=NULL)
                newList->next=newList->next->next;
            oldList=oldList->next;
        }
        return newHead;
    }
};